Date modified: Mon 2023-05-15 . 09:26 AM
Date created: Sat 2023-10-07 . 09:02 PM
# Flip graphs of convex polygons. Consider a convex polygon $P$ in the plane, and consider all its triangulations. For an $n$-gon, it is famously known that the number of triangulations is given by the **Catalan numbers** $C_{n-2}$, where $C_n = \frac{1}{n+1}{2n \choose n}$. For instance, here are the $\frac{1}{5}{8 \choose 4} = 14$ triangulations of a convex hexagon: ![[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 08.52.05.excalidraw.svg]] %%[[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 08.52.05.excalidraw|🖋 Edit in Excalidraw]], and the [[---files/Flip-graphs-of-convex-polygons 2023-05-14 08.52.05.excalidraw.dark.svg|dark exported image]]%% Now define an operation called **flip** for each diagonal, where we turn one diagonal between two triangles, into the diagonal across it: ![[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 09.17.16.excalidraw.svg]] %%[[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 09.17.16.excalidraw.md|🖋 Edit in Excalidraw]], and the [[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 09.17.16.excalidraw.dark.svg|dark exported image]]%% Note what is obtained is another triangulation of the same $n$-gon, and this process is reversible. Now if we take all the triangulations of one convex $n$-gon, and create a **graph** where each vertex is one of the triangulations, and join an edge between two if they can be obtained from one another via a flip. This is called the **flip graph** of this polygon. For instance, here is the flip graph of a convex hexagon: ![[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 09.22.02.excalidraw.svg]] %%[[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 09.22.02.excalidraw.md|🖋 Edit in Excalidraw]], and the [[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 09.22.02.excalidraw.dark.svg|dark exported image]]%% It is easy to be convinced that in such a flip graph for a convex $n$-gon, each vertex of the graph is of degree $n-3$, since there are $n-3$ many diagonals to flip. One also observes that this graph is connected. That is to say, one can perform a series of flips to get to any triangulation from any triangulation. Let us see why this is the case. It suffices to show that every triangulation can get to one common triangulation. Let us let $T_0$ be a triangulation of convex $n$-gon $P$ where all diagonals are joined to some fixed vertex $v_0$ on $P$. Now take any triangulation $T$ of $P$. The number of triangles incidence at $v_0$ is between $1$ and $n-2$. If there are $n-2$ triangles meeting at $v_0$ then this is the triangulation $T_0$. If it is less than $n-2$, then this means one of the triangles has its side opposing $v_0$ an internal diagonal (and not the side of $P$), so we flip that diagonal and increase the number of triangles incident at $v_0$, until it is maximal, which we obtain $T_0$. Here is an illustration: ![[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 10.20.30.excalidraw.svg]] %%[[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 10.20.30.excalidraw.md|🖋 Edit in Excalidraw]], and the [[0 inbox/---files/Flip-graphs-of-convex-polygons 2023-05-14 10.20.30.excalidraw.dark.svg|dark exported image]]%% Hence flip graphs for convex $n$-gons are connected! --- There are other curiosities. What about flip graphs for triangulations for higher dimensional polytopes? Are they connected? Also the flip graph of the convex hexagon itself look like a 3-polytope. Indeed, it is something called an **associahedron**, that lives in $n-3$ space for the convex $n$-gon. #graph-theory #catalan